package graph.bipartite;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Classname : IsGraphBipartite
 * @Description :
 * <a href="https://leetcode.cn/problems/is-graph-bipartite/">785. 判断二分图</a><br/>
 * 染色法：用两种颜色对图种节点遍历染色，若所有相邻节点颜色不同，则图二分
 * @Author : chentianyu
 * @Date 2023/2/1 22:00
 */


public class IsGraphBipartite {

    private final int UNCOLOR = 0;
    private final int RED = 1;
    private final int GREEN = 2;

    /**
     * 广度优先搜索遍历染色
     *
     * @param graph
     * @return
     */
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        Queue<Integer> q = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (color[i] != UNCOLOR) continue;
            q.offer(i);
            color[i] = RED;
            while (!q.isEmpty()) {
                int cur = q.poll();
                for (int next : graph[cur]) {
                    if (color[next] == UNCOLOR) {
                        color[next] = (color[cur] == RED ? GREEN : RED);
                        q.offer(next);
                    } else {
                        if (color[cur] == color[next]) return false;
                    }
                }
            }
        }
        return true;
    }


    /**
     * 深度优先搜索遍历染色
     *
     * @param graph
     * @return
     */
    public boolean isBipartite2(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        for (int i = 0; i < n; i++) {
            if (color[i] == UNCOLOR) {
                if (!dfs(graph, color, i)) return false;
            }
        }
        return true;
    }

    private boolean dfs(int[][] graph, int[] color, int cur) {
        for (int next : graph[cur]) {
            if (color[next] == UNCOLOR) {
                color[next] = (color[cur] == RED ? GREEN : RED);
                if (!dfs(graph, color, next)) return false;
            } else {
                if (color[next] == color[cur]) return false;
            }
        }
        return true;
    }
}
